package _10_binary_tree.order.depth;

import _10_binary_tree.TreeNode;
import org.junit.Test;

/**
 * @author: mornd
 * @dateTime: 2023/6/11 - 14:37
 * 递归实现深度优先遍历，前，中，后
 */
public class RecursionOrderTest {
    /**
     * 构建树
     *          1
     *         /\
     *        2  3
     *       /  /\
     *      4  5  6
     * @return
     */
    static TreeNode genericTestTree() {
        return new TreeNode(1, new
                TreeNode(2,
                    new TreeNode(4), null),
                new TreeNode(3,
                        new TreeNode(5),
                        new TreeNode(6)));
    }

    @Test
    public void test() {
        // 1,2,4,3,5,6
        System.out.print("前序遍历结果：");
        preOrder(genericTestTree());
        // 4,2,1,5,3,6
        System.out.print("\n中序遍历结果：");
        inOrder(genericTestTree());
        // 4,2,5,6,3,1
        System.out.print("\n后序遍历结果：");
        postOrder(genericTestTree());
    }

    /**
     * 前序遍历
     * @param node
     */
    void preOrder(TreeNode node) {
        if(node == null) {
            return;
        }
        System.out.print(node + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    /**
     * 中序遍历
     * @param node
     */
    void inOrder(TreeNode node) {
        if(node == null) {
            return;
        }
        inOrder(node.left);
        System.out.print(node + " ");
        inOrder(node.right);
    }

    /**
     * 后续遍历
     * @param node
     */
    void postOrder(TreeNode node) {
        if(node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node + " ");
    }
}
